package com.algorithm.union;

/**
 * @Author: DOWN
 * @Date: 2022/5/12 15:07
 * @Comment: 并查集-快速查询版
 */
public class UnionFindSets implements IUnionFind {

    private int[] id;

    public UnionFindSets(int size) {
        id = new int[size];
        for (int i = 0; i < id.length; i++) {
            id[i] = i;
        }
    }

    /**
     * 获取元素个数
     * @return int
     */
    @Override
    public int getSize() {
        return id.length;
    }

    /**
     * 获取对应的集合id
     * @param p 元素
     * @return id
     */
    private int find(int p) {
        if (p < 0 || p >= id.length) {
            throw new IllegalArgumentException("p is out of bound!.");
        }
        return id[p];
    }

    /**
     * 校验元素间是否关联
     * @param p 元素
     * @param q 元素
     * @return  boolean
     */
    @Override
    public boolean isConnectes(int p, int q) {
        return find(p) == find(q);
    }

    /**
     * 关联不同的 元素-集合
     * @param p 元素
     * @param q 元素
     */
    @Override
    public void unionElements(int p, int q) {
        int pid = find(p);
        int qid = find(q);
        if (qid != pid) {
            for (int i = 0; i < id.length; i++) {
                if (id[i] == pid) {
                    id[i] = qid;
                }
            }
        }
    }
}
